package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

/**
 * 654.最大二叉树
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 *  1.创建一个根节点，其值为 nums 中的最大值。
 *  2.递归地在最大值 左边 的 子数组前缀上 构建左子树。
 *  3.递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 */
public class BiTree18_ConstructMaximumBinaryTree {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        TreeNode treeNode = constructMaximumBinaryTree(nums);
        // 先序遍历打印这棵二叉树
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(treeNode));
    }

    private static TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildBinaryTree(nums, 0, nums.length - 1);
    }

    // 递归构建二叉树：前序遍历
    private static TreeNode buildBinaryTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        // 数组最大值下标
        int maxNumIndex = getNumsMaxIndex(nums, left, right);
        // 构建根节点
        TreeNode root = new TreeNode(nums[maxNumIndex]);
        // 根据 maxNumIndex 划分左右子树，递归构建
        root.left = buildBinaryTree(nums, left, maxNumIndex - 1);
        root.right = buildBinaryTree(nums, maxNumIndex + 1, right);
        
        return root;
    }

    // 找到数组指定区间内的最大值索引
    private static int getNumsMaxIndex(int[] nums, int left, int right) {
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }

}
